package com.cty._01_Base._07_ConstructBinaryTree;

/**
 * @Auther: cty
 * @Date: 2020/6/28 9:29
 * @Description: 面试题7：重建二叉树
 * 题目：输入某二叉树前序遍历和中序遍历结果，请重建该二叉树。假设输入的前序遍历和中序
 * 遍历结果中都不含重复的数字。例如，输入前序遍历序列{1,2,4,7,3,5,6,8}和中中序遍历序
 * 列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的头节点。
 * @version: 1.0
 */
public class ConstructBinaryTree {
    /**
     * 重建二叉树
     * @param preorder
     * @param inorder
     * @param length
     * @return
     */
    public static BinaryTreeNode rebuildTree(int[] preorder, int[] inorder, int length) throws Exception {
        // 1 前序序列和中序序列为空
        if(preorder==null || inorder==null || length<=0)
            return null;

        return recRebuildTree(preorder, 0, length-1, inorder, 0, length-1);
    }

    /**
     * 递归实现重建二叉树
     * @param preorder
     * @param startPreorder
     * @param endPreorder
     * @param inorder
     * @param startInorder
     * @param endInorder
     * @return
     */
    private static BinaryTreeNode recRebuildTree
    (int[] preorder, int startPreorder, int endPreorder,
     int[] inorder, int startInorder, int endInorder) throws Exception {

        // 当前根节点
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = preorder[startPreorder];
        root.leftChild = root.rightChild = null;

        // 结束条件：
        if(startPreorder == endPreorder){  // 3 二叉树只有一个节点
            if(preorder[startPreorder] == inorder[startInorder])
                return root;
            else
                throw new Exception("Invalid input.");  // 2 前序序列和中序序列不匹配
        }

        // 从中序序列中查找根节点
        int rootInorder = startInorder;
        while(rootInorder<=endInorder && inorder[rootInorder]!=root.value)
            rootInorder++;

        if(rootInorder > endInorder)
            throw new Exception("Invalid input.");  // 2 前序序列和中序序列不匹配

        int leftLength = rootInorder - startInorder;
        int leftPreorderEnd = startPreorder + leftLength;

        if(leftLength > 0){
            // 构建左子树
            root.leftChild = recRebuildTree(preorder,startPreorder+1,leftPreorderEnd,
                    inorder,startInorder, rootInorder-1);
        }

        if(leftLength < endPreorder-startPreorder){
            // 构建右子树
            root.rightChild = recRebuildTree(preorder,leftPreorderEnd+1, endPreorder,
                    inorder,rootInorder+1, endInorder);
        }

        return root;
    }  // end recRebuildTree()

}  // end class
